package 简单算法;

/**
 * @Author: 胡成
 * @Version: 0.0.1V
 * @Date: 2019-05-16
 * @Description: 给定一个排序的整数数组（升序）和一个要查找的整数target，
 * 用O(logn)的时间查找到target第一次出现的下标（从0开始），
 * 如果target不存在于数组中，返回-1
 **/
public class 二分查找 {
    public static void main(String[] args) {
        二分查找 s = new 二分查找();
        System.out.println(s.binarySearch(new int[]{1, 2, 4, 6, 8, 9, 10}, 7));
    }

    public int binarySearch(int[] nums, int target) {
        // write your code here
        if (nums.length == 0) {
            return -1;
        }
        //起始索引和最后索引
        int start = 0, end = nums.length - 1;
        while (start < end) {
            int mid = start + (end - start) / 2;
            if (nums[mid] == target) {
                end = mid;
            } else if (nums[mid] < target) {
                //向右移一位在计算二分查找
                start = mid + 1;
            } else {
                //向左移一位在计算二分查找
                end = mid - 1;
            }
        }

        if (nums[start] == target) {
            return start;
        }

        return -1;

    }
}
